package leetcode.code2029;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution3 implements IDebug {

	boolean Alice = true;
	boolean Bob = false;

	public boolean stoneGameIX(int[] stones) {
		int len = stones.length;
//		int l = 0;
//		int r = len - 1;
//		while (l < r) {
//			if (stones[l] % 3 == 0) {
//				this.swap(stones, l, r);
//				r--;
//			} else {
//				l++;
//			}
//		}
		int sum = 0;
		for (int num : stones) {
			sum += num;
		}
//		System.out.println(sum + " " + sum % 3);
		Boolean[][][] hash = new Boolean[2][len + 1][sum + 1];
		return this.stoneGameIX(stones, Alice, len, 0, hash, 0);
	}

	private boolean stoneGameIX(int[] stones, boolean who, int end, int total, Boolean[][][] hash, int used) {
		if (end == 0) {
			return this.Bob;
		}

		int index = who ? 0 : 1;
		if (hash[index][used][total] != null) {
			return hash[index][used][total];
		}
		for (int i = 0; i < end; i++) {
			int sum = stones[i] + total;
			if (sum % 3 != 0) {
				this.swap(stones, i, end - 1);
				if (this.stoneGameIX(stones, !who, end - 1, sum, hash, used + 1) == who) {
					hash[index][used][total] = who;
					System.out.println(who + " " + used + " " + total + " " + who);
					return who;
				}
				this.swap(stones, i, end - 1);
			}
		}
		hash[index][used][total] = !who;
		System.out.println(who + " " + used + " " + total + " " + !who);
		return !who;
	}

	private void swap(int[] stones, int i, int j) {
		int tmp = stones[i];
		stones[i] = stones[j];
		stones[j] = tmp;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.stoneGameIX(HelpDebug.str2array3("[2,1]")));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(false, this.stoneGameIX(HelpDebug.str2array3("[2]")));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(false, this.stoneGameIX(HelpDebug.str2array3("[5,1,2,4,3]")));
	}

	@Override
	public void debug4() {
		HelpDebug.compare(true, this.stoneGameIX(HelpDebug.str2array3("[2,2,1,2,3,4,5,6,1,1,1]")));

	}

	public void debug5() {
		HelpDebug.compare(true, this.stoneGameIX(HelpDebug.str2array3(
				"[77,74,12,63,95,23,19,91,48,87,26,22,21,30,41,10,22,80,14,36,62,29,13,3,15,47,71,1,95,21,43,84,62,70,10,86,70,9,38,30,51,32,75,87,73,8,54,64,35,22,68,75,4,59,69,82,27,9,20,32,64,59,58,48,32,21,15,20,75]")));

	}

	public void debug6() {
		HelpDebug.compare(true, this.stoneGameIX(HelpDebug.str2array3("[1,1,7,10,8,17,10,20,2,10]")));

	}

	public void debug7() {
		HelpDebug.compare(true, this.stoneGameIX(HelpDebug.str2array3("[7,10,1,9,19,17,1,9,19]")));

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
//		so.debug5();
//		so.debug6();
		so.debug7();
	}

}
